//
// Created by Mr.J on 2019/11/7.
//
#include <iostream>
#include <vector>
#include <string>
using namespace std;

bool isPla(string s){
//    cout<<s<<endl;
    short a = 0,b = s.size()-1;
    while(a<b){
        if(s[a++] != s[b--])return false;
    }
    return true;
}

int minCut(string s){
    short l = s.size();
    int result[l+1];
    result[0] = 0;
    for (int k = 0; k < l; ++k)result[k] = k;
    for (int i = 1; i <= l; ++i) {
        for (int j = 0; j < i; ++j) {
            if(isPla(s.substr(j,i-j))){
                result[i] = min(result[j],result[i]);
            }
        }
    }
    return result[l];
}

int main(){
    cout<<minCut("abcbaaaa");
    return 0;
}
